1. Field of the Invention
The present invention relates to an encoding method, more particularly to an encoding method to a self-orthogonal quasi-cyclic (QC) code.
2. Description of Related Art
Generally, in the majority of a recording/reproducing apparatus and a communication apparatus, an attempt has been made to reduce a bit-error rate (BER) of digital transmission information by transmitting a code sequence obtained by encoding an input information sequence.
FIG. 1 is a block diagram for showing a common recording/reproducing apparatus or a common communication apparatus in which any digital signal processing is performed.
In FIG. 1, first, an information sequence from a user is input to an encoding section 1a of a recording or transmission device 1. The encoding section 1A encodes the information sequence at a ratio of k/n to provide a code sequence. It is to be noted that k is an information word length, n is a code word length, and k/n is referred to as a code rate or a coding rate. Encoding is often carried out, involving a plurality of encoding schemes such as encryption, error correction coding, and run-length limited coding.
The encoding section 1A transmits the code sequence to a recording section 1B (or a transmission section 1B) of the recording or transmission device 1. In a case of a recording/reproducing system, for example, the recording section 1B receives and records the code sequence as a recorded signal on a recording medium, not shown, by using an optical pickup, a magnetic head, and the like. In a case of a wireless communication system, for example, the transmission section 1B receives and transmits the code sequence as a transmission signal to the air space through a transmission antenna in the transmission section 1B.
The recorded signal or the transmission signal is input to a reproducing section 2A (or a reception section 2A) of a reproducing or reception device 2. In a case of the recording/reproducing system, the reproducing section 2A reads the recorded signal out of the recording medium, not shown, with an analog optical pickup or an analog magnetic head to convert it into an analog reproduced signal. In the case of the wireless communication system, the reception section 2A receives and converts the transmission signal in the air space into an analog reception signal through a reception antenna.
These analog signals are equalized to any predetermined target equalization characteristics by using an analog equalizer, not shown, and then converted into a digital reception signal in an A/D conversion section 2B per time. It is to be noted that the A/D conversion section 2B includes a phase-locked loop circuit, not shown. A code detection section 2C receives the digital reception signal and converts it into a detected code sequence or its posterior probability information sequence. A decoding section 2D receives and decodes the sequences into detected information words at a ratio of n/k, to provide a detected information sequence.
However, if equalization by the analog equalizer is not sufficient, a digital equalizer may be provided between the A/D conversion section 2B and the code detection section 2C in some cases. Further, recently, in the code detection section 2C, generally a soft-decision detector such as a Viterbi detector has been used. In the case where repeated decoding is employed in the decoding section 2D, a posterior probability detector may be used in the code detection section 2C in some cases.
A variety of codes have been discussed as the codes which are used in the encoding section 1A and the decoding section 2D shown in FIG. 1, some of which have been commercialized including a Reed-Solomon (RS) code, etc. Recently, as one of error correction codes which are used in the encoding section 1A and the decoding section 2D of FIG. 1 to reduce a BER of transmission information effectively, a low-density parity-check (LDPC) code has been studied greatly. The LDPC code has long been known since it was proposed by R. G. Gallager in 1961. Recently, it has become clear that the LDPC code has a very excellent decoding performance. Details of the LDPC code are disclosed in a literature, “Low Density Parity Check Codes,” by R. G. Gallager, MIT Press, Cambridge, Mass., 1963.
This LDPC code refers to a parity-check code in which its parity-check matrix (hereinafter referred to as “check matrix” simply) has a sparse number of is. Therefore, the LDPC code is a name that is applicable to a very wide range of such codes that the number of 1s in their check matrix is just defined ambiguously to some extent. Therefore, it does not refer to a code that complies with specific code generation rules like an RS code generally well known, for example. That is, there are very many so-called LDPC codes that have the same code word length or parity length. To decode LDPC codes, generally, one of repeated decoding methods referred to as a sum-product decoding method or a belief-propagation (BP) decoding method is applied.
To obtain a good BER when the BP decoding method is applied to the LDPC codes, it is preferable that its check matrix should have as few short cycles as possible. The smallest number of cycles in a matrix is four. Therefore, to reduce a post-decoding BER for LDPC codes, it is known that its check matrix preferably includes no four-cycles. Here, terms, “a binary matrix whose element is {0, 1} has a four-cycle” means that when arbitrary two columns are selected in a matrix, at least two row in which both of the two columns have 1 are present.
If a check matrix of a code has no four-cycle, this code is referred to as “a self-orthogonal code”. In many cases, in the self-orthogonal code, resultantly its check matrix has a sparse number of is, so that this code can be utilized as an LDPC code. Further, it is known that the self-orthogonal code is one-step majority-logic decodable. Supposing a minimum column weight in a check matrix to be w, it is known that a minimum hamming distance (hereinafter referred to as “minimum distance”) dmin of a self-orthogonal code is given by the following Equation (1). It is to be noted that a column weight refers to a total number of is in a column in a case of a binary matrix.dmin≧w+1  (1)
Further, an upper limit of a code word length n of a self-orthogonal code having a check matrix with a constant column weight is known as a Steiner limit and given by the following Equation (2) using w and the number of rows m of the check matrix.
                    n        ≤                              m            ⁡                          (                              m                -                1                            )                                            w            ⁡                          (                              w                -                1                            )                                                          (        2        )            
In the LDPC code, generally, to reduce a post-decoding BER, preferably the minimum distance of the code is as large as possible, while to reduce a circuit scale of the decoder, preferably the column weight is as small as possible. However, in many cases, an increase in minimum distance leads to an increase in column weight, thereby resulting in complexity of the decoder. That is, in the LDPC code, if a post-decoding BER is improved, such the improvement is liable to lead to an increase in circuit scale of the relevant encoder and decoder.
Recently, as one method for solving this, it has been focused that a time-honored quasi-cyclic (QC) code is used as an LDPC code. This QC code has a very high regularity of a check matrix, so that by utilizing this regularity, the QC code, when used as the LDPC code, is expected to reduce a circuit scale of the relevant encoder and decoder. It is to be noted that a QC code refers to such a code that a sequence obtained by cyclically shifting an arbitrary code word by a certain period p different from a length of the code word may provide a code word other than the original code word. A QC code, if p=1 is established in particular, is referred to as “a cyclic code”. It is also possible to make the QC code self-orthogonal (see a literature, “Self-Orthogonal Quasi-Cyclic Codes” by R. Townsend and E. Weldon, Jr., IEEE Trans. Info. Theory, vol. IT-13, no. 2, pp. 183-195, April 1967).
A check matrix of the QC code can be expressed using a p's integral multiple of circulant matrices. Generally, a circulant matrix composed of m number of rows and m number of columns (m-by-m circulant matrix) is defined as such a matrix that every column of it can be obtained by cyclically shifting an arbitrary column, for example, a first column. That is, if a leftmost first column vector of an m-by-m circulant matrix C is defined as [x0, x1, . . . , xm−1]T (T indicates transposition operation), C is expressed as follows.
                    C        =                  (                                                                      x                  ⁢                                                                          ⁢                  0                                                                              x                                      m                    -                    1                                                                                                x                                      m                    -                    2                                                                              ⋯                                                              x                  ⁢                                                                          ⁢                  1                                                                                                      x                  ⁢                                                                          ⁢                  1                                                                              x                  ⁢                                                                          ⁢                  0                                                                              x                                      m                    -                    1                                                                              ⋯                                                              x                  ⁢                                                                          ⁢                  2                                                                                                      x                  ⁢                                                                          ⁢                  2                                                                              x                  ⁢                                                                          ⁢                  1                                                                              x                  ⁢                                                                          ⁢                  0                                                            ⋯                                                              x                  ⁢                                                                          ⁢                  3                                                                                    ⋮                                            ⋮                                            ⋮                                            ⋱                                            ⋮                                                                                      x                                      m                    -                    1                                                                                                x                                      m                    -                    2                                                                                                x                                      m                    -                    3                                                                              ⋯                                                              x                  ⁢                                                                          ⁢                  0                                                              )                                    (        3        )            
However, although each of the columns of the circulant matrix C is circulated downward in the Equation (3), they may be circulated upward in definition. An inverse matrix of a circulant matrix and a product of two circulant matrices provide a circulant matrix.
In this case, if an m-by-p matrix Di (0≦i<m) is defined as a matrix whose j'th column (0≦j<p) is composed of the i'th columns of p number of m-by-m circulant matrices Cj, one of check matrices Hp of a QC code having a period p can be expressed as follows:Hp=(D0D1 . . . Dm−1)  (4)
Using a very simple shift register circuit enables any information to be encoded as the QC code (see a literature, “Self-Orthogonal Quasi-Cyclic Codes,” by R. Townsend and E. Weldon, Jr., IEEE Trans. Info. Theory, vol. IT-13, no. 2, pp. 183-195, April 1967 and U.S. Pat. Nos. 3,475,724 and 6,928,602.
So far, several theories for designing a QC code that is available as an LDPC code have been known. As one of the theories, finite geometry has been known. This finite geometry may mainly come in Euclidean geometry (EG) and projective geometry (PG). A code designed in accordance with the finite geometry is referred to as a finite geometry code.
A check matrix of the finite geometry matrix code is composed on the basis of points that are present on lines in a space, so that the finite geometry matrix code is defined as 1 if points are present and as 0 otherwise. Considering GF(2qs) that has a Galois field GF (2s) as a subspace, m-dimensional Euclidean geometry on the Galois field GF (2s) having 2s number of points on one line is expressed as EG (q, 2s). Further, considering GF (2(q+1)s) that has a Galois field GF (2s) as a subspace, q-dimensional projective geometry having 2s+1 number of points on one line is expressed as PG (q, 2s).
A finite geometry code has been known for long as a majority-logic decodable circulant code; for example, a (272, 190) shortened difference set circulant code obtained by shortening by one bit a (273, 191) difference set circulant code based on a projective geometry PG (2, 24) has been realized as an error correction code for use in multiplex telecasting in Japan. It is to be noted that n of an (n, k) code indicates a code word length and k thereof indicates an information word length. Although finite geometry codes include a code that is majority-logic decodable at two stages or more, such the codes are not self-orthogonal. A method for using a self-orthogonal finite geometry code as an LDPC code is disclosed in a literature, “Low Density Parity Check Codes on Finite Geometries: A Rediscovery and New Results,” by Y. Kou, S. Lin and M. Fossorier, IEEE Trans. Info. Theory, vol. 47, no. 7, pp. 2711-2735, November 2001.
In this literature, a code that has a transposed matrix of a check matrix of a finite geometry code as its check matrix is referred to as “a type-II code of finite geometry codes” and the fact that some of such type-II codes are useful as an LDPC code is pointed out. It is be noted that a finite geometry code becomes a circulant code and its type-II code becomes a QC code and further a type-II code of self-orthogonal finite geometry codes is self-orthogonal. Hereinafter, a finite geometry code and its type-II code are each referred to as “a code based on finite geometry”.
In self-orthogonal QC codes based on the finite geometry, if p≧2, generally, a relationship of dmin=w+1 is established. However, if a binary code is given, whether its minimum distance is not larger than a certain hamming distance dH or not can be checked as follows. That is, when dH number (s) of columns is (are) extracted from a check matrix, it is enough only to give only one example of such a combination that modulo2 of a total number of 1s in each of the rows may be 0 in all rows. Further, in this case, if dH=w+1 and the code is self-orthogonal, its minimum distance can be determined to be w+1 from the Equation (1).
As another theory that is available to a design of a QC code, for example, a time-honored method based on combinatorics referred to as balanced incomplete block design (BIBD) has been known. A method for configuring an LDPC code according to the BIBD is disclosed in a literature, “Construction of Low-Density Parity-Check Codes Based on Balanced Incomplete Block Designs,” by B. Ammar, B. Honary, Y. Kou, J. Xu and S. Lin, IEEE Trans. Info. Theory, vol. 50, no. 6, pp. 1257-1268, June 2004. However, projective geometry classified into an infinite family is one of the BIBD approaches.
A code configured in accordance with BIBD includes a QC code partially but is not whole of the QC code.
Discussion to make a minimum distance of a self-orthogonal code not limited to a QC code configured in accordance with the BIBD larger than w+1 has been often carried out so far in the case of w=3. It is known that if all of columns of a check matrix have the same weight and w=3, by removing all code words that constitute hamming distance 4 from a self-orthogonal code, its minimum distance becomes at least 6. A configuration of a check matrix of such a code is referred to as “an anti-Pasch configuration”.
In combinatorics, a Pasch configuration is referred to also as a quadrilateral and refers to such a configuration that a union of four triple-points of a Steiner triple system is constituted of a set of six points. In other words, the Pasch configuration means that the four triple-points are give in formats of {x0, x1, x2}, {x0, x4, x5}, {x1, x3, x5}, and {x2, x3, x4}. An STS including no Pasch configuration is referred to as an anti-Pasch configuration or a quadrilateral-free configuration. Details of the anti-Pasch configuration are disclosed in a literature, “Anti-Pashe Steiner Triple Systems,” by T. S. Griggs, J. Murphy and J. S. Phelan, J. of Combinatories, Information & System Sciences, vol. 15, pp. 79-84, 1990.
I, however, believe that no QC code that has an anti-Pasch configuration with w=3 in a check matrix in the Equation (4) has yet been reported. Further, in a self-orthogonal code based on the finite geometry or the BIBD, the code word length and the number of parity bits of a code that can be designed are restrictive.
A report has been made so far of a self-orthogonal QC code which is designed with arbitrary code word length and number of parity bits without using any finite geometry or BIBD and whose minimum distance is larger than w+1, that is, which has an established relationship given by:dmin≧w+2  (5)in a case where w=2, for example (see United States Patent Application Publication No. US2004/0093549.
A QC code has been known to surely include six cycles if w≧3; however, the six-cycles can be removed therefrom only if w=2. If four-cycles and six-cycles are removed from a QC code with w=2, its minimum distance becomes at least four. A method of the above US Patent Application Publication has disclosed a design of a code that satisfies the above Equation (5) by utilizing such a peculiarity that six-cycles can be removed only if w=2.
Thus, it has been known that a self-orthogonal QC code is effectively available to any use as one method for simplifying an encoding/decoding circuit for an LDPC code, and the finite geometry and the BIBD are representative theories for designing the self-orthogonal QC code.